home *** CD-ROM | disk | FTP | other *** search
RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) NNNNaaaammmmeeee RWTPtrHashTable<T> - Rogue Wave library class SSSSyyyynnnnooooppppssssiiiissss #include <rw/tphasht.h> unsigned hashFun(const T&); RWTPtrHashTable<T> table(hashFun); PPPPlllleeeeaaaasssseeee NNNNooootttteeee!!!! IIIIffff yyyyoooouuuu ddddoooo nnnnooootttt hhhhaaaavvvveeee tttthhhheeee SSSSttttaaaannnnddddaaaarrrrdddd CCCC++++++++ LLLLiiiibbbbrrrraaaarrrryyyy,,,, uuuusssseeee tttthhhheeee iiiinnnntttteeeerrrrffffaaaacccceeee ddddeeeessssccccrrrriiiibbbbeeeedddd hhhheeeerrrreeee.... OOOOtttthhhheeeerrrrwwwwiiiisssseeee,,,, uuuusssseeee tttthhhheeee iiiinnnntttteeeerrrrffffaaaacccceeee ttttoooo RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhMMMMuuuullllttttiiiiSSSSeeeetttt described in the Class Reference. DDDDeeeessssccccrrrriiiippppttttiiiioooonnnn This class implements a parameterized hash table of types T. It uses chaining to resolve hash collisions. Duplicates are allowed. It is a ppppooooiiiinnnntttteeeerrrr based collection: pointers to objects are copied in and out of the hash buckets. Parameter TTTT represents the type of object to be inserted into the table, either a class or fundamental type. The class TTTT must have: well-defined equality semantics (TTTT::::::::ooooppppeeeerrrraaaattttoooorrrr========((((ccccoooonnnnsssstttt TTTT&&&&))))). A user-supplied hashing function for type TTTT must be supplied to the constructor when creating a new table. If TTTT is a Rogue Wave class, then this requirement is usually trivial because most Rogue Wave objects know how to return a hashing value. In fact, classes RRRRWWWWCCCCSSSSttttrrrriiiinnnngggg, RRRRWWWWDDDDaaaatttteeee, RRRRWWWWTTTTiiiimmmmeeee, and RRRRWWWWWWWWSSSSttttrrrriiiinnnngggg contain static member functions called hhhhaaaasssshhhh that can be supplied to the constructor as is. The function must have prototype:.Ex unsigned hhhhFFFFuuuunnnn(const T& a); and should return a suitable hash value for the object aaaa. To find an object, it is first hashed to determine in which bucket it occurs. The bucket is then searched for an object that is equal (as determined by the equality operator) to the candidate. The initial number of buckets in the table is set by the constructor. There is a default value. If the number of items in the collection greatly exceeds the number of buckets then efficiency will sag because each bucket must be searched linearly. The number of buckets can be changed by calling member function rrrreeeessssiiiizzzzeeee(((()))). This is relatively expensive because all of the keys must be rehashed. If PPPPaaaaggggeeee 1111 RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) you wish for this to be done automatically, then you can subclass from this class and implement your own special iiiinnnnsssseeeerrrrtttt(((()))) and rrrreeeemmmmoooovvvveeee(((()))) functions which perform a rrrreeeessssiiiizzzzeeee(((()))) as necessary. PPPPeeeerrrrssssiiiisssstttteeeennnncccceeee None EEEExxxxaaaammmmpppplllleeee #include <rw/tphasht.h> #include <rw/cstring.h> #include <rw/rstream.h> main() { RWTPtrHashTable<RWCString> table(RWCString::hash); RWCString *states[4] = { new RWCString("Alabama"), new RWCString("Pennsylvania"), new RWCString("Oregon"), new RWCString("Montana") }; table.insert(states[0]); table.insert(states[1]); table.insert(states[2]); table.insert(states[3]); RWCString key("Oregon"); cout << "The table " << (table.contains(&key) ? "does " : "does not ") << "contain Oregon0; table.removeAll(&key); cout << "Now the table " << (table.contains(&key) ? "does " : "does not ") << "contain Oregon"; delete states[0]; delete states[1]; delete states[2]; delete states[3]; return 0; } Program output The table does contain Oregon Now the table does not contain Oregon .Ex PPPPuuuubbbblllliiiicccc CCCCoooonnnnssssttttrrrruuuuccccttttoooorrrrssss RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee<T>(unsigned (*hashFun)(const T&), size_t buckets = RWDEFAULT_CAPACITY); PPPPaaaaggggeeee 2222 RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) Constructs an empty hash table. The first argument is a pointer to a user-defined hashing function for items of type TTTT.... The table will initally have bbbbuuuucccckkkkeeeettttssss buckets although this can be changed with member function rrrreeeessssiiiizzzzeeee(((()))). RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee<T>(const RWTPtrHashTable<T>& c); Constructs a new hash table as a shallow copy of cccc. After construction, pointers will be shared between the two collections. The new object will have the same number of buckets as cccc. Hence, the keys will not be rehashed. PPPPuuuubbbblllliiiicccc OOOOppppeeeerrrraaaattttoooorrrrssss RWTPtrHashTable& ooooppppeeeerrrraaaattttoooorrrr====(const RWTPtrHashTable<T>& c); Sets self to a shallow copy of cccc. Afterwards, pointers will be shared between the two collections and self will have the same number of buckets as cccc. Hence, the keys will not be rehashed. void PPPPuuuubbbblllliiiicccc MMMMeeeemmmmbbbbeeeerrrr FFFFuuuunnnnccccttttiiiioooonnnnssss aaaappppppppllllyyyy(void (*applyFun)(T*, void*), void* d); Applies the user-defined function pointed to by aaaappppppppllllyyyyFFFFuuuunnnn to every item in the table. This function must have prototype: void yyyyoooouuuurrrrFFFFuuuunnnn(T* a, void* d); Client data may be passed through as parameter dddd. The items should not be changed in any way that could change their hash value. void cccclllleeeeaaaarrrr(); Removes all items from the collection. void cccclllleeeeaaaarrrrAAAAnnnnddddDDDDeeeessssttttrrrrooooyyyy(); PPPPaaaaggggeeee 3333 RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) Removes all items from the collection aaaannnndddd deletes them. RWBoolean ccccoooonnnnttttaaaaiiiinnnnssss(const T* p) const; Returns TTTTRRRRUUUUEEEE if the collection contains an item which is equal to the item pointed to by pppp. Returns FFFFAAAALLLLSSSSEEEE otherwise. Equality is measured by the class-defined equality operator for type TTTT. size_t eeeennnnttttrrrriiiieeeessss() const; Returns the number of items currently in the collection. T* ffffiiiinnnndddd(const T* target) const; Returns a pointer to the object which is equal to the object pointed to by ttttaaaarrrrggggeeeetttt, or nnnniiiillll if no such object can be found. Equality is measured by the class-defined equality operator for type TTTT. void iiiinnnnsssseeeerrrrtttt(T* a); Adds the object pointed to by aaaa to the collection. RWBoolean iiiissssEEEEmmmmppppttttyyyy() const; Returns TTTTRRRRUUUUEEEE if the collection has no items in it, FFFFAAAALLLLSSSSEEEE otherwise. size_t ooooccccccccuuuurrrrrrrreeeennnncccceeeessssOOOOffff(const T* a) const; Returns the number of objects in the collection which are equal to the object pointed to by aaaa. Equality is measured by the class-defined equality operator for type TTTT. T* rrrreeeemmmmoooovvvveeee(const T* a); Removes the object which is equal to the object pointed to by aaaa and returns a pointer to it, or nnnniiiillll if no such object could be found. Equality is measured by the class-defined equality operator for type TTTT. PPPPaaaaggggeeee 4444 RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) RRRRWWWWTTTTPPPPttttrrrrHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333CCCC++++++++)))) size_t rrrreeeemmmmoooovvvveeeeAAAAllllllll(const T* a); Removes all objects which are equal to the object pointed to by aaaa. Returns the number of objects removed. Equality is measured by the class-defined equality operator for type TTTT. void rrrreeeessssiiiizzzzeeee(size_t N); Changes the number of buckets to NNNN. This will result in all of the objects in the collection being rehashed. PPPPaaaaggggeeee 5555 
